#include <iostream>
#include <vector>
#include <cassert>

template<typename T>
bool isSorted(const std::vector<T>& arr)
{
    if(arr.size()<=1)
    {
        return true;
    }
    for (size_t i = 1; i < arr.size(); i++) {
        if (arr[i] < arr[i-1]) {
            return false;
        }
    }
    return true;
}

template<typename T, typename Compare>
bool isSorted(const std::vector<T>& arr, Compare comp)
{
    if (arr.size() <= 1) {
        return true;
    }
    
    for (size_t i = 1; i < arr.size(); i++) {
        if (comp(arr[i], arr[i-1])) {
            return false;
        }
    }
    return true;
}

//1.merge sort
//2.button-up sort
//3.针对不同的key，在c++中怎么实现
template<typename T>
void merge(std::vector<T> & a,std::vector<T> & aux,int lo,int mid,int hi)
{
    //assert(isSorted());
    //assert [mid+1,hi]
    for(int k=lo;k<=hi;k++)
        aux[k] = a[k];
    int i = lo,j = mid + 1;
    for(int k=lo;k<=hi;k++)
    {
        if(i>mid) a[k]=aux[j++];
        else if(j>hi)  a[k]=aux[i++];
        else if(aux[j] < aux[i]) a[k]=aux[j++];
        else a[k]=aux[i++];
    }
    //assert [lo,hi]
}

template<typename T>
void sort(std::vector<T> & a,std::vector<T> & aux,int lo,int hi)
{
    if(hi<=lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a,aux,lo,mid);
    sort(a,aux,mid+1,hi);
    merge(a,aux,lo,mid,hi);
}

template<typename T>
void botton_up_sort(std::vector<T> & a,std::vector<T> & aux)
{
    int N = a.size();
    for(int sz = 1;sz < N;sz+=sz)
    {
        for(int lo=0;lo < N-sz;lo+=sz+sz)
        {
            merge(a,aux,lo,lo+sz-1,std::min(lo+sz+sz-1,N-1));
        }
    }
}

int main()
{
    std::vector<int> a = {64, 25, 12, 22, 11};
    std::vector<int> aux(a.size());
    //sort(a,aux,0,a.size()-1);
    botton_up_sort(a,aux);

    std::cout << "排序后的数组: ";
    for (int a : a) {
        std::cout << a << " ";
    }
    std::cout << std::endl;
}